import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;


@SuppressWarnings("unchecked")
public class board {
	
	//get the system newline character
	public static final String NL = System.getProperty("line.separator");

	// array of 81 cells (0-80)
	public cell cells[] = new cell[81];
	
	// arrays of ArrayLists
	public ArrayList<cell> rows[] = new ArrayList[9];
	public ArrayList<cell> cols[] = new ArrayList[9];
	public ArrayList<cell> blks[] = new ArrayList[9];
	
	private boolean _isDirty = false;
	private boolean _isSolved = false;
	
	private void SolveCheck() {
		if (_isSolved) { return; }
		boolean s = true;
		for (int i = 0; i < 81; i++) {
			if (cells[i].getValue() == 0) { s = false; }
		}
		_isSolved = s;
		if (_isSolved) { System.out.println("Board is Solved"); }
	}

	
	
	// generic constuctor:  all cells unknown (bitmask = 511, value = 0)
	public board() {
		init();
	}
	
	/* parameterized constructor...
	 *   requires a string of 81 chars representing the values of the cells
	 *   or a string of 243 chars representing the 3-digit bitmask of each cell
	 */
	public board(String s) throws Exception {
		if (!(s.length() == 81 || s.length() == 243)) {throw new Exception("Input String must be 81 or 243 chars. (" + s.length() + ")");}
		// by default, all cells are unknown
		init();
		
		// setting cells by 81-char value string
		if (s.length() == 81) {
			// loop 0-80 for the string and the cells
			for (int i=0; i < 81; i++) {
				//try to cast the character to an integer.  if successful, set that cell's value.
				//  will work for values 0-9 (0=unknown)
				try {
					int x = Integer.parseInt(String.valueOf(s.charAt(i)));
					if (0 < x & x < 10) { cells[i].setValue(x); }
				}
				catch(Exception e) { } //do nothing, leave the cell unknown (works for non-numeric chars)
			}
		}
		else { // setting cells by 243-char state string
			// loop 0-80 for the cells
			for (int i=0; i < 81; i++) {
				//substring starts at 3*i and ends at 3*i+3
				cells[i].setBitmask(Integer.parseInt(s.substring(3*i,3*i+3)));
				
			}
		}
		
	}
	
	//set up the cells, rows, cols, and blks
	private void init() {
		for (int i=0; i < 9; i++) {
			rows[i] = new ArrayList();
			cols[i] = new ArrayList();
			blks[i] = new ArrayList();
		}
		
		for (int i=0; i < 81; i++) { 
			cells[i] = new cell();
			cells[i].setID(i);
			//add the cell to the appropriate row/col/blk
			cell thiscell = cells[i];
			int r = thiscell.getRow();
			int c = thiscell.getCol();
			int b = thiscell.getBlk();
			rows[r].add(thiscell);
			cols[c].add(thiscell);
			blks[b].add(thiscell);
		}
	}
	
	public void Rule2() {
		System.out.println("Running Rule2.");
		_isDirty = false;
		if (_isSolved) { return; }
		
		for (int i = 0; i < 81; i++) {
			
			
			cell me = cells[i];
			
			if (me.getValue() > 0) {continue;}
			
			//get row, col, and block from the cell
			int r = me.getRow();
			int c = me.getCol();
			int b = me.getBlk();
			
			for (cell x : rows[r]) {
				if (!(x.getID() == i)) { 
					int v = x.getValue();
					if (v > 0) {
						if (me.isBitSet(v)) {
							System.out.println("Rule2:Cell(" + i + "):Row(" + r + "): Clearing Value(" + v + ") because it exists in row at cell(" + x.getID() + ")");
							me.clearBit(v);
							_isDirty = true;
						}
					}			
				}
			}
			
			for (cell x : cols[c]) {
				if (!(x.getID() == i)) { 
					int v = x.getValue();
					if (v > 0) {
						if (me.isBitSet(v)) {
							System.out.println("Rule2:Cell(" + i + "):Col(" + c + "): Clearing Value(" + v + ") because it exists in col at cell(" + x.getID() + ")");
							me.clearBit(v);
							_isDirty = true;
						}
					}			
				}			
			}
			
			for (cell x : blks[b]) {
				if (!(x.getID() == i)) { 
					int v = x.getValue();
					if (v > 0) {
						if (me.isBitSet(v)) {
							System.out.println("Rule2:Cell(" + i + "):Blk(" + r + "): Clearing Value(" + v + ") because it exists in blk at cell(" + x.getID() + ")");
							me.clearBit(v);
							_isDirty = true;
						}
					}			
				}	
			}
		}
		SolveCheck();
		if (_isSolved) { return; }
		if (_isDirty) {
			System.out.println("Board has changed.");
			Rule2();
		}
		if (_isSolved) { return; }
		System.out.println("Board has not changed.");
	}
	
	
	public String toStringByRow(int r) {
		String t = "";
		
		for (int i = 0; i < 9; i++) {
			t += String.format("%03d", rows[r].get(i).getBitmask());
		}
		return t;
	}
	public String toStringByCol(int c) {
		String t = "";
		
		for (int i = 0; i < 9; i++) {
			t += String.format("%03d", cols[c].get(i).getBitmask());
		}
		return t;
	}
	public String toStringByBlk(int b) {
		String t = "";
		
		for (int i = 0; i < 9; i++) {
			t += String.format("%03d",blks[b].get(i).getBitmask());
		}
		return t;
	}

	
	//return a string representing all cells
	public String toString() {
		String t = "";
		for (int i = 0; i < 81; i++) { t += cells[i].getValue(); }
		return t.replaceAll("0", ".") + NL;
	}
	
	//return a string representing the row distribution (human-friendly compact)
	public String toStringRows() {
		String t = "";
		for (int i=0; i < 81; i++) { t += cells[i].getRow(); }
		return toStringCompact(t);
	}
	
	//return a string representing the col distribution (human-friendly compact)
	public String toStringCols() {
		String t = "";
		for (int i=0; i < 81; i++) { t += cells[i].getCol(); }
		return toStringCompact(t);
	}
	
	//return a string representing the blk distribution (human-friendly compact)
	public String toStringBlks() {
		String t = "";
		for (int i=0; i < 81; i++) { t += cells[i].getBlk(); }
		return toStringCompact(t);
	}
	
	//return a string representing the whole board (human-friendly compact)
	public String toStringVals() {
		String t = "";
		for (int i=0; i < 81; i++) { t += cells[i].getValue(); }
		t = t.replaceAll("0", ".");
		return toStringCompact(t);
	}
	
	//return a string representing the whole board with current bitmask state
	public String toStringState() {
		String t = "";
		for (int i=0; i < 81; i++) { t += String.format("%03d", cells[i].getBitmask()); }	
		return t;
	}
	
	//return a string representing the whole board (human-friendly with possible values)
	public String toStringFull() {
		String DoubleLine = " ===== ===== ===== ===== ===== ===== ===== ===== ===== ";
		String SingleLine = " ----- ----- ----- ----- ----- ----- ----- ----- ----- ";
		//start with a double line for the top
		String t = DoubleLine + NL;
		/* loop i 0-8 (each row of cells)  the start/end values passed to toStringRow(start,end) represent the
		   cell's index in cells[]
		     i=0, start i*9 = 0, end i*9+8 = 8  (cells 0-8)
		     i=1, start i*9 = 9, end i*9+8 = 17 (cells 9-17) */
		for (int i = 0; i < 9; i++) {
			//get the 3 lines representing these cells
			t += toStringRow(i*9, (i*9) + 8);
			//if we are in row 2,5, or 8(last) then follow with a double line border, otherwise a single line
			t += (i == 2 || i == 5 || i == 8 ) ? DoubleLine + NL : SingleLine + NL;
		}		
		return t + NL;
	}
	
	/* returns a string representing a row of cells:
		| 123 : 123 :     | 123 :     : 123 |     : 123 : 123 | (top: a=0)
		| 456 : 456 :  3  | 456 :  2  : 456 |  6  : 456 : 456 | (mid: a=1)
		| 789 : 789 :     | 789 :     : 789 |     : 789 : 789 | (bot: a=2)
	*/
	private String toStringRow(int start, int end) {
		String t = "";
		// loop a 0-2.  will get cell substrings 0-3, 3-6, 6-9 or top,middle,bottom
		for (int a = 0; a < 3; a++) {
			//first cell in a row has a left-most pipe border
			t += "| " + cells[start].toString().substring(a*3, a*3 + 3) + " " ;
			//middle cells of a row have a left-most colon border, unless it is cell #4 or 7, which have pipes
			for (int i = start + 1 ; i < end; i++) {
				t += (i == start + 3 || i == start + 6) ? "| " : ": ";
				t += cells[i].toString().substring(a*3, a*3 + 3) + " ";
			}
			//last cell of a row has a left-most column border and a right-most pipe border
			t += ": " + cells[end].toString().substring(a*3, a*3 + 3) + " |" + NL;
		}
		return t;
	}
	
	private String toStringCompact(String s) {
		String t = "";
		for (int i=0; i < 9; i++) {
			t += s.substring(i*9, i * 9 + 9) + NL;
		}
		return t;
	}
	
}
